#include <iostream>
#include <cassert>

using namespace std;

// 3. Longest Substring Without Repeating Characters
// https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
//
// 滑动窗口的另一个实现, 仅做参考
// 时间复杂度: O(len(s))
// 空间复杂度: O(len(charset))
class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {

        int freq[256] = {0}; // 记录字符是否出现过

        int l = 0, r = -1; // 滑动窗口为s[l...r]，初始为1个无效窗口
        int res = 0;

        // 在这里, 循环中止的条件可以是r + 1 < s.size(), 想想看为什么?
        while (r + 1 < s.size())
        {
            // 先把右边的指针移到不能移
            while (r + 1 < s.size() && freq[s[r + 1]] == 0)
                freq[s[++r]]++;

            res = max(res, r - l + 1);

            // 开始来动左边的指针
            if (r + 1 < s.size())
            {
                freq[s[++r]]++;
                assert(freq[s[r]] == 2);
                while (l <= r && freq[s[r]] == 2)
                    freq[s[l++]]--;
            }
        }
        return res;
    }
};

int main()
{
    cout << Solution().lengthOfLongestSubstring("abcabcbb") << endl; // 3
    cout << Solution().lengthOfLongestSubstring("bbbbb") << endl;    // 1
    cout << Solution().lengthOfLongestSubstring("pwwkew") << endl;   // 3
    cout << Solution().lengthOfLongestSubstring("c") << endl;        // 1
    cout << Solution().lengthOfLongestSubstring("") << endl;         // 0

    return 0;
}